package P150;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author LiangMu
 * @version \$Id: P47.java, v 0.1, 2024年07月06日 14:53 LiangMu Exp $$
 */
public class P47 {

    public static int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) {
            return new int[][]{newInterval};
        }
        List<int[]> left = new ArrayList<>();
        List<int[]> right = new ArrayList<>();
        for (int[] ints : intervals) {
            int direct = getDirect(ints, newInterval);
            if (direct == -1) {
                left.add(ints);
            } else if (direct == 1) {
                right.add(ints);
            } else {
                newInterval[0] = Math.min(newInterval[0], ints[0]);
                newInterval[1] = Math.max(newInterval[1], ints[1]);
            }
        }
        left.add(newInterval);
        left.addAll(right);
        return left.toArray(new int[0][0]);
    }

    private static int getDirect(int[] target, int[] newInsert) {
        if (newInsert[0] > target[1]) {
            return -1;
        } else if (newInsert[1] < target[0]) {
            return 1;
        } else {
            return 0;
        }
    }

    public static void main(String[] args) {
        int[][] intervals = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
        int[] newInterval = {4, 8};
        System.out.println(Arrays.deepToString(insert(intervals, newInterval)));
    }
}
